package linked_list;

public class LinkedList {

     private ListNode head;
     private ListNode tail;

     private int count;
     //头插法
     public void addFirst(int data){
          count++;
          ListNode node = new ListNode(data);
          if(head == null) {
               head = node;
               tail = head;
               return;
          }
          node.next = head;
          head.prev = node;
          head = node;
     }
     //尾插法
     public void addLast(int data){
          count++;
          ListNode node = new ListNode(data);
          if(tail == null) {
               tail = node;
               head = tail;
               return;
          }
          node.prev = tail;
          tail.next = node;
          tail = node;
     }
     private boolean isIndexOutOfAdd(int index) {
          return index < 0 || index > size();
     }

     private ListNode find(ListNode start, int data) {
          if(start == null) {
               return null;
          }
          while(start != null) {
               if(start.val == data) {
                    break;
               }
               start = start.next;
          }
          return start;
     }

     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data){
          if(isIndexOutOfAdd(index)) {
               return false;
          }
          if(index == 0) {
               addFirst(data);
               return true;
          }
          if(index == size()) {
               addLast(data);
               return true;
          }
          count++;
          ListNode cur = head;
          ListNode node = new ListNode(data);
          while(index-- > 0) {
               cur = cur.next;
          }
          node.prev = cur.prev;
          node.next = cur;
          cur.prev.next = node;
          cur.prev = node;
          return true;
     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
          return find(head, key) != null;
     }

     // 当只在最后一个元素的时候要删除
     private void removeWhenOne() {
          tail = head = null;
          count--;
     }
     private void removeFirst() {
          if(tail == head) {
               removeWhenOne();
               return;
          }
          count--;
          head = head.next;
          head.prev = null;
     }
     private void removeLast() {
          if(tail == head) {
               removeWhenOne();
               return;
          }
          count--;
          tail = tail.prev;
          tail.next = null;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
          ListNode cur = find(head, key);
          if(cur.next == null) {
               removeLast();
          } else if(cur.prev == null) {
               removeFirst();
          } else {
               ListNode prev = cur.prev;
               ListNode next = cur.next;
               prev.next = cur.next;
               next.prev = cur.prev;
               count--;
          }
     }
     //删除所有值为key的节点
     public void removeAllKey(int key){
          while(head != null && head.val == key) {
               removeFirst();
          }
          while(tail != null && tail.val == key) {
               removeLast();
          }

          ListNode cur = head;
          while((cur = find(cur, key)) != null && cur.next != null) {
               ListNode prev = cur.prev;
               ListNode next = cur.next;
               prev.next = cur.next;
               next.prev = cur.prev;
               count--;
          }


     }
     //得到单链表的长度
     public int size(){
          return count;
     }
     public void display(){
          ListNode cur = head;
          while(cur != null) {
               System.out.print(cur.val + " ");
               cur = cur.next;
          }
          System.out.println(size() == 0 ? "null" : "");
     }

     public void displayOfLast(){
          ListNode cur = tail;
          while(cur != null) {
               System.out.print(cur.val + " ");
               cur = cur.prev;
          }
          System.out.println(size() == 0 ? "null" : "");
     }
     public void clear(){
          while(head != null) {
               removeLast();
          }
          count = 0;
     }
 }